/*************************************************************************
	> File Name: shell_sort.cpp
	> Author: 
	> Mail: 
	> Created Time: Tue 06 Aug 2024 03:09:02 PM CST
 ************************************************************************/

#include <cstdio>
#include <cstdlib>
#include "0.sort_test.h"

void unguardedInsertSort(int *arr, int l, int r, int step = 1) {
    int index = l;
    for(int i = l + step; i < r; i += step) {
        if(arr[i] < arr[index]) index = i;
    }
    // swap(arr[l], arr[index]); 破坏插入排序稳定
    while(index > l) {
        swap(arr[index], arr[index - step]);
        index -= step;
    }
    for(int i = l + step; i < r; i += step) {
        index = i;
        while(arr[index] < arr[index - step]) {
            swap(arr[index], arr[index - step]);
            index -= step;
        }
    }
    return ;
}

void shellSort(int *arr, int l, int r) {
	int k = 2, n = (r - l), step;
	do {
		step = ((n / k) == 0) ? 1 : (n / k);
		for(int i = l; i < l + step; i++) {
			unguardedInsertSort(arr, i, r, step);
		}
		k *= 2;
	} while(step != 1);
    return ;
}

void hibbardShellSort(int *arr, int l, int r) {
    int step = 1, n = (r - l);
    while(step <= (n / 2)) step = 2 * step + 1;
    do {
        step /= 2;
        for(int i = l; i < l + step; i++) {
			unguardedInsertSort(arr, i, r, step);
		}
    } while (step > 1);
    return ;
}

int main() {
    int *arr = getRandData(BIG_DATA);
	TEST(shellSort,        arr, BIG_DATA);
    TEST(hibbardShellSort, arr, BIG_DATA);
    free(arr);
    return 0;
}
